package com.echo.boot.structure.algorithm.sort.cmp.quick;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA
 * Created By CQ
 * Date: 2020/4/23
 * Time: 12:41
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {3, 5, 1, 9, 2, 8, 4, 7};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    static void sort(int[] arr) {
        int i = 0;
        int j = arr.length - 1;
        sort(arr, i, j);
    }


    static void sort(int[] arr, int i, int j) {
        if (j <= i) {
            return;
        }
        int partition = partition(arr, i, j);
        sort(arr, i, partition - 1);
        sort(arr, partition + 1, j);

    }

    static int partition(int[] arr, int i, int j) {
        int pivot = arr[i];
        int left = i;
        int right = j + 1;
        while (true) {
            while (arr[--right] > pivot) {
                if (right == left) {
                    break;
                }
            }
            while (pivot > arr[++left]) {
                if (left == right) {
                    break;
                }
            }
            if (left >= right) {
                break;
            } else {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        int temp = arr[i];
        arr[i] = arr[right];
        arr[right] = temp;
        return right;
    }
}
